class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
stack<TreeNode*> f;
    vector<int> ans;
    TreeNode* st = root;
    
    while (st != NULL) {
        while (st != NULL) {//入栈时写
            ans.push_back(st->val);
            f.push(st);
            st = st->left;
        }
        //确保stack进入没有NULL
        if (!f.empty()) {
            do {
                st = f.top();
                f.pop();
            } while (!f.empty() && st->right == NULL);
            if (st != NULL) {
                st = st->right;
            }
        }

    }
    return ans;
    }
};